package daily;

public class Solution121 {
    public static void main(String[] args) {
        Solution121 solution = new Solution121();
        long result = solution.maxProfit(new int[] {7, 1, 5, 3, 6,  4});
        System.out.println(result);
    }

    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[] minPrice = new int[len];
        minPrice[len-1] = prices[len-1];
        for (int i = len-2; i >= 0; i --) {
            minPrice[i] = Math.max(prices[i+1], minPrice[i+1]);
        }

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < len; i ++) {
            max = Math.max(max, minPrice[i] - prices[i]);
        }
        return max;
    }
}
